package com.coderdream.chapter10.strategy.a4a;

public class QuickSorter implements Sorter {

	Comparable[] data;

	public void sort(Comparable[] data) {
		this.data = data;
		this.qsort(0, data.length - 1);
	}

	private void qsort(int pre, int post) {
		int saved_pre = pre;
		int saved_post = post;

		Comparable mid = data[(pre + post) / 2];

		do {
			while (data[pre].compareTo(mid) < 0) {
				pre++;
			}
			while (mid.compareTo(data[post]) < 0) {
				post--;
			}

			if (pre <= post) {
				Comparable tmp = data[pre];
				data[pre] = data[post];
				data[post] = tmp;
				pre++;
				post--;
			}
		} while (pre <= post);

		if (saved_pre < post) {
			this.qsort(saved_pre, post);
		}

		if (pre < saved_post) {
			this.qsort(pre, saved_post);
		}
	}
}
